#include <vector>
#include <string>
#include <iostream>

using std::vector;
using std::string;
using std::cout;
using std::endl;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ret;
        vector<int> tmp;
        vector<int> flag(n, 0);
        dfs(ret, tmp, flag, 1, n);
        return ret;
    }

    void dfs(vector<vector<string>>& v, vector<int>& tmp, vector<int>& flag, int cur, int n) {
        if (cur > n) {
            vector<string> q;
            for (int i : tmp) {
                string s = "";
                int count = i - 1;
                while (count > 0) {
                    s += '.';
                    count--;
                }
                s += 'Q';
                count = n - i;
                while (count > 0) {
                    s += '.';
                    count--;
                }
                q.push_back(s);
            }
            v.push_back(q);
        }
        else {
            for (int i = 1; i <= n; i++) {
                if (flag[i - 1]) {
                    continue;
                }
                bool fix = true;
                for (int j = 1; j < cur; j++) {
                    if (abs(i - tmp[j - 1]) == cur - j) {
                        fix = false;
                        break;
                    }
                }
                if (fix) {
                    tmp.push_back(i);
                    flag[i - 1] = 1;
                    dfs(v, tmp, flag, cur + 1, n);
                    flag[i - 1] = 0;
                    tmp.pop_back();
                }
            }
        }
    }
};